#include<bits/stdc++.h>
using namespace std;

/**
 * 主函数，实现区间最大值与最小值查询的算法。
 */
int main() {
    // 声明变量
    long long n, a, s[500005] = {0}, q, l, r, k;
    long long d[500005][25] = {0}, x[500005][25] = {0};

    // 第一步：读入序列的长度
    scanf("%lld", &n);

    // 第二步：遍历序列，计算前缀和并初始化最大值和最小值数组
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a);
        s[i] = s[i - 1] + a; // 计算第i个位置的前缀和
        d[i][0] = x[i][0] = s[i]; // 初始化最大值和最小值数组的第一列
    }

    // 第三步：读入查询数量
    scanf("%lld", &q);

    // 第四步：使用动态规划预处理区间最大值和最小值
    // 这里利用了二进制表示，从长度为2^i的子区间开始，逐步扩展到整个区间
    for (int i = 1; i <= log2(n); i++) // 对于每一个2的幂次的区间长度
        for (int j = 0; j + (1 << i) - 1 <= n; j++) { // 对于每一个可能的起始位置j
            // 更新区间最大值，通过比较当前区间的两个子区间最大值
            d[j][i] = max(d[j][i - 1], d[j + (1 << (i - 1))][i - 1]);
            // 更新区间最小值，通过比较当前区间的两个子区间最小值
            x[j][i] = min(x[j][i - 1], x[j + (1 << (i - 1))][i - 1]);
        }

    // 第五步：处理每个查询
    while (q--) {
        // 读入查询的左边界和右边界
        scanf("%lld%lld", &l, &r);
        l--; // 左边界减一，因为数组下标从0开始

        // 第六步：计算区间长度的对数值，用于快速查找预处理的最大值和最小值
        k = log2(r - l + 1);

        // 第七步：根据预处理的结果，计算查询区间内的最大值和最小值
        // 并输出区间和的绝对值
        // 这里利用了预处理的最大值和最小值数组，通过比较两个子区间的最大值和最小值来得到最终结果
        printf("%lld\n", abs(max(d[l][k], d[r - (1 << k) + 1][k]) - min(x[l][k], x[r - (1 << k) + 1][k])));
    }
}
